package leetcode.editor.cn;

//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。
//
//
//
// 示例 1：
//
//
//输入：haystack = "sadbutsad", needle = "sad"
//输出：0
//解释："sad" 在下标 0 和 6 处匹配。
//第一个匹配项的下标是 0 ，所以返回 0 。
//
//
// 示例 2：
//
//
//输入：haystack = "leetcode", needle = "leeto"
//输出：-1
//解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
//
//
//
//
// 提示：
//
//
// 1 <= haystack.length, needle.length <= 10⁴
// haystack 和 needle 仅由小写英文字符组成
//
//
// Related Topics 双指针 字符串 字符串匹配 👍 2371 👎 0

//Java：找出字符串中第一个匹配项的下标
public class FindTheIndexOfTheFirstOccurrenceInAString {
    public static void main(String[] args) {
        Solution solution = new FindTheIndexOfTheFirstOccurrenceInAString().new Solution();
        int i = solution.strStr("hello", "ll");
        System.out.println(i);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        public int strStr(String haystack, String needle) {
            //长度小于待匹配子串
            if (haystack == null || needle == null) {
                return -1;
            }
            if (needle.isEmpty()) {
                return 0;
            }
            if (haystack.length() < needle.length()) {
                return -1;
            }

            int[] dp = new int[needle.length()];
            getNext(needle, dp);
            int i = 0;
            int j = 0;
            while (i < haystack.length()) {
                char hc = haystack.charAt(i);
                char nc = needle.charAt(j);
                if (hc == nc) {
                    j++;
                    i++;
                }
                if (j == needle.length()) {
                    return i - needle.length();
                }
                if (nc != hc) {
                    if (j == 0 && i < haystack.length()) {
                        //j已经是0，没办法后退了，只能i前进了
                        i++;
                    } else {
                        j = dp[j - 1 < 0 ? 0 : j - 1];
                    }
                }


            }
            return -1;
        }

        private void getNext(String needle, int[] dp) {
            int j = 0; // 前缀指针
            dp[0] = 0; // dp数组初始化

            for (int i = 1; i < needle.length(); i++) {
                while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                    j = dp[j - 1]; // 匹配失败，回退j
                }
                if (needle.charAt(i) == needle.charAt(j)) {
                    j++;
                }
                dp[i] = j; // 更新dp数组
            }
        }


    }

//    class Solution {
//        public int strStr(String haystack, String needle) {
//            if (haystack == null || needle == null) {
//                return -1;
//            }
//            if (needle.length() == 0) {
//                return 0;
//            }
//            if (haystack.length() < needle.length()) {
//                return -1;
//            }
//
//            int[] dp = new int[needle.length()];
//            getNext(needle, dp);
//
//            int i = 0; // 指向haystack的指针
//            int j = 0; // 指向needle的指针
//
//            while (i < haystack.length()) {
//                if (haystack.charAt(i) == needle.charAt(j)) {
//                    i++;
//                    j++;
//                }
//                if (j == needle.length()) {
//                    return i - j; // 匹配成功，返回起始索引
//                } else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {
//                    if (j > 0) {
//                        j = dp[j - 1]; // 匹配失败，根据dp数组回退j
//                    } else {
//                        i++; // j已经为0，无法回退，移动i
//                    }
//                }
//            }
//
//            return -1; // 匹配失败
//        }
//
//        private void getNext(String needle, int[] dp) {
//            int j = 0; // 前缀指针
//            dp[0] = 0; // dp数组初始化
//
//            for (int i = 1; i < needle.length(); i++) {
//                while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
//                    j = dp[j - 1]; // 匹配失败，回退j
//                }
//                if (needle.charAt(i) == needle.charAt(j)) {
//                    j++;
//                }
//                dp[i] = j; // 更新dp数组
//            }
//        }
//    }
//leetcode submit region end(Prohibit modification and deletion)

}
